from typing import Optional

from solution.common.tree_node import TreeNode


class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        # 此值表示的不是最大边的数量，而是最大边对应的节点的数量，因此最终结果是此值-1
        self.maxDiameter = 1
        # 深度函数：有一个节点，则深度视为1，而不是边有多少
        def depth(root):
            # 如果当前节点为空，则深度为0
            if not root:
                return 0
            # 获取左子树的深度
            left = depth(root.left)
            # 获取右子树的深度
            right = depth(root.right)
            # 直径节点数，由已维护值，与左子树深度+右子树深度+当前节点
            self.maxDiameter = max(self.maxDiameter, left + right + 1)
            # 当前树的深度，是左子树与右子树的深度的最大值，+1获得
            return 1 + max(left, right)
    
        depth(root)
        return self.maxDiameter - 1